An encryption method is roughly divided into a public key method and a common key method. The public key method uses different keys for encoding and decoding and ensures the security of transmitting information by letting only a receiver know a key for decoding an encoded text (private key) instead of publicly opening a key for encoding (public key). However, the common key method uses the same key for encoding and decoding and ensures the security of transmitting information by preventing the private key from being known by a third party other than a transmitter and a receiver.
When the encryption of a common key (hereinafter called a “common key encryption”) is compared with the encryption of a public key (hereinafter called an “public key encryption”), the common key encryption has an advantage that its process speed is fast and it can be compactly installed. Therefore, when an encryption function is added to a small-size device, such as a cellular phone, an IC card and the like, a common key encryption is used. Since its process speed is high and it can encode/decode information in real time, it can be also used for information communications in the fields of broadcast and communications.
The common key encryption is divided into stream cipher and block cipher. The block cipher divides a plaintext (text to be encoded) into groups with a certain bit length (called a “block”) and encodes it in units of groups. The bit length of a block being the process unit of encryption is called a “block length”.
As to the common key block cipher, various algorithms are known according to its block length. DES, AES, SC2000, MISTY 1, MISTY 2, KASUMI and the like are its typical ones. These common key encryption algorithms are installed by software or hardware.
Next, MISTY 1 being one piece of common key encryption will be explained. The MISTY 1 is common key encryption with a block length of 64 bits and a key length of 128 bits. The MISTY 1 is publicly opened, for example, on the home page of IPA (Information-technology Promotion Agency) (see Non-patent document 1).
FIG. 1 is a basic configuration of a MISTY 1 encryption process. FIG. 1 is obtained by simplifying FIG. 1A of Non-patent document 1.
As illustrated in FIG. 1, MISTY 1 is Feistel type encryption. The MISTY 1 includes an FL function 10, an FO function 20 and an exclusive OR 30, and is composed by combining these components. In the MISTY 1, a first Feistel structure 100 including two FL functions 10, one FO function 20 and one exclusive OR 30 and a second Feistel structure 200 including one FO function and one exclusive OR 30 are alternately vertically multi-stage-connected. The number n of stages of the MISTY 1 is regulated to be a multiple of four and n=8 is recommended.
As illustrated in FIG. 1, in the MISTY 1, the first Feistel structure 100 is assigned to the odd number and the second Feistel structure 200 is assigned to the even number. The first Feistel structure 100 and the second Feistel structure 200 both include an FO function 20.
Next, a Feistel structure will be briefly explained. The Feistel structure is configured in such a way as to divide an input into two of left and right blocks, to input one block on the L side (hereinafter called a “block L”) to an F function (FO function 20 in the case of MISTY 1), to calculate the exclusive OR of the output of the F function and the other block on the R side (hereinafter called a “block R”) and to replace the blocks L and R with each other after the completion of the logic calculation process.
In the case of MISTY 1, the first Feistel structure 100 applies the processes of an FL function 10L (FL1) and an FL function 10R (FL2) to the blocks L (32 bits) and the blocks R (32 bits) to the block R (32 bits), respectively, and inputs the process results to the exclusive OR 30. Then, the process result of the FL function 10L and the logical calculation result of the exclusive OR 30 are outputted to a Feistel structure 200 in a subsequent stage as blocks R and L, respectively.
The second Feistel structure 200 inputs the blocks L and R to the FO function 20 and the exclusive OR 30, respectively. Then, the exclusive OR of the above process result of the FO function 20 and the above block R is calculated by the exclusive OR 30 and the logical calculation result and the above block L are outputted to outside. In this case, the above block and the above logical calculation result are inputted to a Feistel structure in a subsequent structure 100 as blocks R and L, respectively.
The FL functions 10 and 20 are a key-dependent non-linear function and a non-linear function, respectively. The FL function 10 is a function in a Feistel structure which converts 32-bit input data to 32-bit data using a 32-bit extended key KL, which is not illustrated, and outputs it. The FO function 20 is the function of a MISTY structure which converts 32-bit input data to 32-bit data using a 64-bit extended key KO, which is not illustrated, and a 48-bit extended key KI, which is not illustrated, and outputs it. As described later, the FO function 20 includes three FI functions inside. This FI function is a non-linear function.
It is important that an encryption device mounted on a small-size device has a small circuit scale. Especially, a circuit scale is emphasized in an embedded micro-controller with an encryption function, an encryption hard accelerator and the like. Therefore, when a common key encryption algorithm in which a MISTY structure is often used, such as MISTY1, KASUMI or the like is implemented by hardware, in order to reduce the circuit scale of the hardware, it is very effective to reduce the circuit scale of an FO function.
FIG. 2A is a “structure 300 including an FO function 20 and an exclusive OR 30 connected to it” extracted from the structure of MISTY 1 in FIG. 1. The structure 300 illustrated in FIG. 2A is a component provided for both of the first Feistel structure 100 and the second Feistel structure 200.
The configuration/operation of the structure 300 will be explained. The structure 300 inputs the data of a 32-bit block L and the data of a 32-bit block R. The data of a 32-bit block L is outputted to outside without applying any process to it and also is inputted to the FO function 20. The FO function 20 converts the data of the block L to 32-bit data using a 64-bit extended key KO, which is not illustrated, and a 48-bit extended key KI, which is not illustrated, and outputs the conversion result to the exclusive OR 30. The exclusive OR 30 calculates the exclusive OR of the data of the block R and the output of the FO function 20 and outputs the logical calculation result (32-bit data) to outside. The structure 300 outputs the inputted data of block L to outside without applying any process to it.
FIG. 2B is a structure obtained by rotating the structure 300 illustrated in FIG. 2A by 90 degrees clockwise. When the FO function inside the structure 310 illustrated in FIG. 2B is developed, a structure illustrated in FIG. 2C is obtained.
The summary of a structure 320 illustrated in FIG. 2C is disclosed as FOi in FIG. 2 of Non-patent document 1. The structure 320 divides the data of a 32-bit block L being one input data into data LL of its higher-order 16 bits and data LR of its lower-order 16 bits. The data of a 32-bit block R being the other input data is also divided into data RL of its higher-order 16 bits and data RR of its lower-order 16 bits. The FO function 20 uses keys KOi1 through KOi4 (16 bits each) being partial bits of a private key K (128 bits) as one input of an exclusive OR 321 provided in the pre-stage of the FI function. Furthermore, extended keys KIi1 through KIi3 (16 bits each) obtained by extracting partial bits from the private key K and applying an extended key generation process to the bits are used for the keys of FI functions (FIi1-FIi3). How to generate the extended keys KOi1 through KOi4 and KIi1 through KIi3 is disclosed in Non-patent document 1. The FO function is the function of a MISTY structure. One of the keys KOi1 through KOi4 and the keys KIi1 through KIi3 is sometimes simply described as a key.
When the structure 320 illustrated in FIG. 2C is analyzed from the viewpoint of a process algorithm, a structure illustrated in FIG. 3 is obtained. In the structure 330 illustrated in FIG. 3 it is assumed that the data (32 bits) of blocks L and R being input data are stored in registers Reg-L and Reg-R, respectively.
The entire process of the FO function 20 can be divided into three cycle of processes which are separated by thick horizontal broken lines in FIG. 3. These three cycles are sequentially called here as a cycle 1, a cycle 2 and a cycle 3. Since the process procedures of the cycles 1 through 3 are almost the same, apart enclosed with a broken-line rectangular frame in FIG. 3 (cycle 1 process unit) can be unitized as hardware and the unit 500 can be commonly used for the respective cycles of processes. Specifically, the processes of cycles 1 through 3 can be performed by performing the above unit 500 three times one after another. Strictly speaking, the process procedures of the cycle 1 and 2 are the same. The cycle 3 calculates the exclusive OR of the process result of the cycle 2 and the key KOi4 by the exclusive OR 321 in addition to the processes of the other cycles (cycles 1 and 2). The structure of the unit 500 is generally called a “MISTY structure”. In the basic configuration of the MISTY structure, an F function (FI function in the case of unit 500) and an exclusive OR are arranged in a left system data path in that order and the above exclusive OR calculates the exclusive of the output of the F function and data branched and inputted from the right system data path. The above output of the exclusive OR is inputted to the right system data path and the data of the right system data path, inputted to the above exclusive OR is inputted to the left system data path in a subsequent stage. In the MISTY structure of the FO function, a first exclusive OR to which a round key KOij (j=1-3) is inputted is arranged on the left system data path, an FI function to which a round key KIij (j=1-3) is arranged in its lower section and a second exclusive OR is arranged its further lower section. Then, the exclusive OR of the output of the FI function and data branched and inputted from the right system data path is calculated by the second exclusive OR. Then, the calculation result of the second exclusive OR is inputted to the right system data path in a subsequent stage. Data flowing through the right system data path in the previous stage is inputted to the left system data path in a subsequent stage. Although the configuration of a MISTY structure is explained above using the MISTY structure of an FO function as an example, there are various forms of MISTY structures obtained by transforming the above basic configuration in data conversion functions other than the FO function, such as an FI function and the like. FIG. 4 is a conventional circuit provided with the function of the unit 500 illustrated in FIG. 3.
The circuit 510 illustrated in FIG. 4 can perform the process of the algorithm illustrated in FIG. 2C. Specifically, the process of an FO function and the process of the exclusive OR of the process result of the FO function and data R can be also possible.
The circuit 510 includes four registers Reg-L, Reg-FOL, Reg-FOR and Reg-R, two multiplexers 511L and 511R, two de-multiplexers 512L and 512R and five exclusive OR calculators 521-525.
The register Reg-L is a 32-bit register and stores 32-bit input data processed by the FO function 20. The higher-order 16 bits (LL) of the data stored in the register Reg-L and the lower-order 16 bits (LR) are inputted to the multiplexers 511L and 511R, respectively. The 16-bit data stored in the register Reg-FOL is also inputted to the multiplexer 511L. The multiplexers 511L selectively outputs the 16-bit data inputted from either the register Reg-L or Reg-FOL to an exclusive OR calculator 521. The exclusive OR calculator 521 calculates the exclusive OR of the 16-bit data inputted from the multiplexer 511L and a 16-bit key KOij (j=1-3) inputted from outside and outputs the calculation result to an FI function processing unit 530. The FI function unit 530 outputs the process result (16-bit data) to an exclusive OR calculator 522. The multiplexer 511R inputs the 16-bit data stored in the register Reg-FOR, selectively outputs 16-bit data inputted from either the register Reg-L or Reg-R to the exclusive OR calculator 522 and the de-multiplexer 512L. The exclusive OR calculator 522 calculates the exclusive OR of the output data (16 bits) of the FI function processing unit 530 and 16-bit data inputted from the multiplexer 511R and outputs the calculation result to the de-multiplexer 512R.
Thus, a circuit including the exclusive OR calculators 521 and 522 provided between the multiplexers 511L and 511R and the de-multiplexers 512L and 512R and the FI function processing unit 530 (circuit 600 enclosed with a broken-line rectangular frame in FIG. 4) has a MISTY structure. Therefore, 16-bit data on the L side (left side), outputted from the de-multiplexer 512L and 16-bit data on the R side (right side), selectively outputted from the multiplexer 511R are replaced with each other by the circuit 600 of a MISTY structure.
The de-multiplexer 512L selectively outputs 16-bit data inputted from the multiplexer 511R to either the register Reg-FOL or the exclusive OR calculator 523. The register Reg-FOL stores 16-bit data inputted from the de-multiplexer 512L and outputs the data to the multiplexer 511L. The exclusive OR calculator 523 is provided to calculate the exclusive OR of an extended key KOi4 in the process of the cycle 3 and an exclusive OR calculation result t3 (see FIG. 2C) in the cycle 2. The logical calculation result of the exclusive OR calculator 523 is outputted to an exclusive OR calculator 524. The higher-order 16 bits (RL) of the 32-bit data R stored in the register Reg-R is also inputted to the exclusive OR calculator 524. The calculation result (16 bits) of the exclusive OR calculator 524 is stored in the register Reg-R as higher-order 16 bit data (RR).
The de-multiplexer 512R outputs the logical calculation result (16 bits) of the exclusive OR calculator 522 to either the register Reg-FOR or the exclusive OR calculator 525. The register Reg-FOR stores 16-bit data inputted from the de-multiplexer 512R and outputs the data to the multiplexer 511R. The exclusive OR calculator 525 calculates the exclusive OR of the lower-order 16 bits (RR) of the 32-bit data R stored in the register Reg-R and input data from the de-multiplexer 512R and outputs the calculation result (16-bit data) to the register Reg-R. The register Reg-R stores 16-bit data inputted from the exclusive OR calculator 525 as the lower-order 16-bit data (RR) of the 32-bit data R and outputs the data RR to the exclusive OR calculator 525.
Thus, a conventional circuit for an FO function and its peripheral circuit (circuit for calculating the exclusive OR of the output of the FO function and data R) requires two registers Reg-FOL and Reg-FOR for storing 16-bit data for the process of the FO function. Specifically, a circuit for an FO function and its peripheral circuit (hereinafter called a “FO function-related processing circuit” for convenience' sake) requires a total 32-bit register for an FO function.
[Algorithm of MISTY 1]
In MISTY 1, a plaintext 1 (64 bits) are divided into two 32 bits. In this case, 32 bits on the MSB (most significant bit) side and 32 bits on the LSB (least significant bit) side are called as L and R, respectively. The respective pieces of divided data L and R are inputted to the first-stage FL functions 10 on the left and right sides, respectively. Then, the output (32 bits) of the above FL functions 10 on the left side is inputted to the first-stage FO function 20 and the output (32 bits) of the above FL functions 10 on the right side becomes one input of the first-stage exclusive OR 30. The output (32 bits) of the first-stage FO function 20 becomes other input of the first-stage exclusive OR 30. The result (32 bits) of the first-stage exclusive OR 30 is inputted to the second-stage FL function 10 on the left side and the second-stage FO function 20. The output (32 bits) of the first-stage FL function 10 on the left side becomes one input of the second-stage exclusive OR 30. The other input of this second-stage exclusive OR 30 is outputted to the above second-stage FO function 20.
[Conventional Process Algorithm of FO Function-Related Processing Circuit]
Next, the process algorithm of an FO function-related processing circuit using a circuit 510 illustrated in FIG. 4 will be explained with reference to FIG. 2C. The following in the right term of each cycle is a symbol indicating an exclusive OR calculation.⊕  [Expression 1]This also applies to logical calculation expressions hereinafter. FI (a, KIij) indicates an FI function process for converting input data ‘a’ by an extended key KIij (j=1-3).
[Cycle 1]t1=FI((LL⊕KOi1),KIi1)⊕LR (to be stored in register Reg-FOR)t2=LR (to be stored in register Reg-FOL)  [Expression 2]
[Cycle 2]t3=FI((t2⊕KOi2),KIi2)⊕t1 (to be stored in a register Reg-FOR)t4=t1 (to be stored in a register Reg-FOL)  [Expression 3]
[Cycle 3]RR=FI((t4⊕KOi3),KIi3)⊕t3⊕RR (to be stored in the lower-order 16 bits of register Reg-R)  [Expression 4]RL=KOi4⊕t3⊕RL (to be stored in the higher-order 16 bits of register Reg-R)  [Expression 5]
As described above, it is necessary that the conventional circuit 510 stores the process results t2i-1 and t2i (i=1-2) of the cycles 1 and 2 in the registers Reg-FOR and Reg-FOL, respectively. However, since the gate scale per bit of a register is larger than that of other devices, in order to reduce the scale of the entire circuit of an encryption device to which MISTY 1 is applied, is preferable to reduce the size of a register as much as possible. This applies to not only MISTY 1 but also a circuit of a block cipher processing device of common key block encryption system having a circuit configuration similar to MISTY 1, such as KASUMI and the like.
FIG. 5 is a flowchart illustrating the software process of the above process algorithm ALp. This software process is performed by a CPU provided with an embedded micro-computer or the like. Data LR, LL, RR and RL and keys KOi1-KOi4 and KIi1-LIi3 which are used in the process of the following flowchart are stored in the register or memory in the CPU.
The process of the flowchart illustrated in FIG. 5 will be explained.
Firstly, the following cycle 1 process of the above process algorithm ALp is performed and the process result is stored in a register A (S1).FI((LL⊕KOi1),KIi1)⊕LR  [Expression 6]The register A is one of general registers provided for the CPU.
Then, the following cycle 2 process of the above process algorithm ALp is performed and the process result is stored in a register B (S2).FI((t2⊕KOi2),KIi2)⊕(contents of register A)  [Expression 7]
Then, lastly, the following cycle 3 process of the above process algorithm ALp is performed and the process result is stored in a “register storing RR”.FI((t4⊕KOi3),KIi3)⊕(Contents of register B)⊕(Contents of register storing RR)  [Expression 8]
Then, the following second cycle 3 process of the above process algorithm ALp is performed and the process result is stored in a “register storing RL”.KOi4⊕(Contents of register B)⊕(Contents of register storing RL)  [Expression 9]
Thus, a 64-bit plaintext is encoded into a 64-bit ciphertext.
FIG. 6 is an example of a program expressing the process of the flowchart illustrated in FIG. 5 by an assembler language. In the program illustrated in FIG. 6, the FI function process is realized by a program (FI-related process function). This FI-related process function is called up from a main program (main routine) illustrated in FIG. 6 as a sub-routine. In FIG. 6, the call-up of this sub-routine is expressed as the following descriptive statement.
Call FI (a, KIij)
j=1-3
The Call FI(a, KIij) is “a process for performing an FI function (FI-related process function) using ‘a’ input data (data to be converted)and KIij as and data conversion key and the process result of the FI function is stored in ‘a’”.
In the program description illustrated in FIG. 6, “MOV” indicate a data transfer instruction and “XOR” indicate an exclusive OR calculation instruction. The operand ‘a’ of these instructions and the argument ‘a’ of the call instruction indicate the register A. The MOV instruction instructs to transfer data specified in a second operand to the register of a first operand. For example, “MOV a, LL” is an instruction to transfer data stored in the register LL to the register A. In addition, “MOV a, [LL]” is an instruction to access a memory address storing data LL and to transfer the data LL from the memory to the register A.
As known from the program description illustrated in FIG. 6, the conventional FO function process program (software) uses two registers (registers A and B) in order to store intermediate data in the course of the data conversion process of a general register provided for the CPU.
Patent document 1: Japanese Laid-open Patent Publication No. 2004-240427
Patent document 2: Japanese Patent No. 3088337 Non-patent document 1: Encryption Technical Specification MISTY 1
Non-patent document 2: Mitsuru Matsui, “Block Cipher Algorithm MISTY”, Technical Report of IEICE, ISEC96-11 (July 1996)